edu.claflin.finder.logic

Class Graph

java.lang.Object

edu.claflin.finder.logic.Graph

Direct Known Subclasses:

ConditionedGraph

public class Graph
extends java.lang.Object

Used to represent a graph in memory. Migrated from matrix form, the graph is now kept track of via a list of edges and nodes. All the previous methods remain in existence but the underlying implementation has changed.

Version:

3.4 February 2, 2016

Author:

Charles Allen Schultz II

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.ArrayList<Edge>	edgeList The list of edges added to the graph.
private java.lang.String	graphName The name of the Graph provided by the user.
private java.util.ArrayList<Node>	nodeList The list of the nodes added to the graph.
protected boolean	suppressLog Used to suppress logging.

Constructor Summary

Constructors

Modifier	Constructor and Description
	Graph(java.lang.String graphName) Initializes the graph.
protected	Graph(java.lang.String graphName, java.util.ArrayList<Node> nodeList, java.util.ArrayList<Edge> edgeList) Private constructor used by subGraph method.

Method Summary

Modifier and Type	Method and Description
boolean	addEdge(Edge edge) Adds an edge to the Graph.
boolean	addEdge(int node1Index, int node2Index, java.lang.Object edgeData) Deprecated. Outdated since v3. Replaced by {}
boolean	addEdge(java.lang.String node1, java.lang.String node2, java.lang.Object edgeData) Deprecated. Outdated since v3. Replaced by {
boolean	addEdges(java.util.List<Edge> edges) Adds a list of Edges to the graph.
boolean	addNewNode(java.lang.String node) Deprecated. Outdated since v3. Replaced by {}
boolean	addNode(Node node) Adds a node to the graph.
boolean	addNodes(java.util.List<Node> nodes) Adds a list of nodes to the graph.
boolean	addPartialGraph(java.util.List<Node> nodes, java.util.List<Edge> edges) Adds a partial graph to this graph.
private void	checkNode(Node node) Verifies that the node is NOT in the graph.
private void	checkNodeIndex(int nodeIndex) Deprecated. No replacement. Further operations shall utilize {)}
Graph	copy() Copies this Graph object using the getSubGraph() method.
java.util.List<Node>	getAdjacencyList(Node node) Obtains an adjacency list for the supplied node based on the Graph.
java.lang.Object	getEdge(int node1Index, int node2Index) Deprecated. Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
Edge	getEdge(Node source, Node destination) Locates an Edge object in the edgeList and returns it.
java.lang.Object	getEdge(java.lang.String node1, java.lang.String node2) Deprecated. Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
java.util.List<Edge>	getEdgeList() Returns the list of edges in the graph.
java.lang.String	getName() Gets the name of the graph.
int	getNodeCount() Gets the number of nodes in the graph.
int	getNodeIndex(Node node) Gets the index of a Node object in memory.
int	getNodeIndex(java.lang.String node) Deprecated. Outdated since v3. Replaced by {}
java.util.List<Node>	getNodeList() Returns the list of nodes in the graph.
java.lang.String	getNodeName(int nodeIndex) Deprecated. Outdated since v3. No replacement. Obtain the Node data via the Node object.
Graph	getSubGraph(java.util.ArrayList<java.lang.String> subStringSet, java.lang.String nameQualifier) Deprecated. Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)
Graph	getSubGraph(int startNode, int stopNode, java.lang.String nameQualifier) Deprecated. Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)
Graph	getSubGraph(java.util.List<Node> nodes, java.lang.String nameQualifier) Returns a subGraph of this graph.
void	transpose(int node1Index, int node2Index) Transposes the specified nodes.
void	transpose(Node node1, Node node2) Transposes the specified nodes.
void	transpose(java.lang.String node1, java.lang.String node2) Deprecated. Outdated since v3. Replaced by {}
Graph	uniqueCopy() Copies this Graph producing a unique copy in which there is no entanglement between the two Graph objects.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

graphName

private final java.lang.String graphName

The name of the Graph provided by the user. This value is used by the program to name output files unless specified otherwise.

nodeList

private final java.util.ArrayList<Node> nodeList

The list of the nodes added to the graph. Used by the program to keep track of the associations within the matrix. It may be re-ordered dynamically at runtime.

edgeList

private final java.util.ArrayList<Edge> edgeList

The list of edges added to the graph. The graph is, by default, a directed graph. As such, two edges must be added to force the graph to be bidirectional.

suppressLog

protected boolean suppressLog

Used to suppress logging.

Constructor Detail

Graph

public Graph(java.lang.String graphName)

Initializes the graph. Merely initializes fields. It does not set any data. Also sets the Logging Utility object. If null, the class will not log data.

Parameters:

graphName - the String which represents the name of the Graph.

Graph

protected Graph(java.lang.String graphName,
                java.util.ArrayList<Node> nodeList,
                java.util.ArrayList<Edge> edgeList)

Private constructor used by subGraph method.

Parameters:

graphName - the String which represents the name of the Graph.

nodeList - the ArrayList of Node objects.

edgeList - the ArrayList of Edge objects.

Method Detail

getName

public java.lang.String getName()

Gets the name of the graph.

Returns:

The graph name.

addNewNode

public boolean addNewNode(java.lang.String node)

Deprecated. Outdated since v3. Replaced by {}

Adds a node to the graph. Adds the specified node name to the nodeList by creating and adding a new node and then calling the addNode(Node) method.

Parameters:

node - the String which denotes the name of the node to add.

Returns:

true if the addition was successful.

addNode

public boolean addNode(Node node)

Adds a node to the graph. Adds a Node object to the graph.

Parameters:

node - the Node object to add.

Returns:

true if the addition was successful.

addNodes

public boolean addNodes(java.util.List<Node> nodes)

Adds a list of nodes to the graph.

Parameters:

nodes - the List<Node> containing the nodes to add.

Returns:

true if the addition was successful.

getNodeIndex

public int getNodeIndex(java.lang.String node)

Deprecated. Outdated since v3. Replaced by {}

Gets the index of a node based on its name. Maintained with the new implementation to preserve existing uses. Will not match nodes which may have additional properties attached in future implementations.

Parameters:

node - the String representing the node to search for.

Returns:

the index of the node or -1 if the node was not found.

getNodeIndex

public int getNodeIndex(Node node)

Gets the index of a Node object in memory. Retained for older API compatibility. The ordering of the nodes is not guaranteed and may change during the program's runtime.

Parameters:

node - the Node object to search for.

Returns:

the index of the node or -1 if the node was not found.

getNodeCount

public int getNodeCount()

Gets the number of nodes in the graph.

Returns:

the integer representing the total number of nodes in the graph.

getNodeName

public java.lang.String getNodeName(int nodeIndex)

Deprecated. Outdated since v3. No replacement. Obtain the Node data via the Node object.

Gets the name of the node at the specified nodeIndex. Ensures that the provided integer is within the range of available indices.

Parameters:

nodeIndex - the integer representing the index to get from the headerList.

Returns:

the String representing the name of the node.

getNodeList

public java.util.List<Node> getNodeList()

Returns the list of nodes in the graph.

Returns:

the List<Node> containing the list of nodes in the graph.

addEdge

public boolean addEdge(int node1Index,
                       int node2Index,
                       java.lang.Object edgeData)

Deprecated. Outdated since v3. Replaced by {}

Adds an edge connecting the specified nodes in the Graph. Sets the object data for the edge dependent upon the supplied parameter.

Parameters:

node1Index - the integer value indicating the first node.

node2Index - the integer value indicating the second node.

edgeData - the Object that represents unique edge data (i.e. weight or edge relationship).

Returns:

true if the addition was successful.

addEdge

public boolean addEdge(java.lang.String node1,
                       java.lang.String node2,
                       java.lang.Object edgeData)

Deprecated. Outdated since v3. Replaced by {

Adds an edge connecting the specified nodes to the Graph. This is a convenience method for adding an edge using node names. Graphs are undirected so the order of the parameters does not matter.

Parameters:

node1 - the String indicating the first node.

node2 - the String indicating the second node.

edgeData - the Object that represents unique edge data (i.e. weight or edge relationship).

Returns:

true if the addition was successful.

addEdge

public boolean addEdge(Edge edge)

Adds an edge to the Graph. If any edge already exists within the Graph connecting the two supplied nodes or either of the two nodes is not in the nodeList, then the edge is not added.

Parameters:

edge - the Edge object to add to the graph.

Returns:

true if the addition was successful.

addEdges

public boolean addEdges(java.util.List<Edge> edges)

Adds a list of Edges to the graph.

Parameters:

edges - the List<Edge> containing the edges to add.

Returns:

true if the addition was successful.

getEdge

public java.lang.Object getEdge(int node1Index,
                                int node2Index)

Deprecated. Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.

Gets the value of the edge between the specified nodes.

Parameters:

node1Index - the integer value of the first node.

node2Index - the integer value of the second node.

Returns:

the Object representing the edge relationship.

getEdge

public java.lang.Object getEdge(java.lang.String node1,
                                java.lang.String node2)

Deprecated. Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.

Gets the value of the edge between the specified nodes. This is a convenience method for getting the edge using the node's String name.

Parameters:

node1 - the String of the first node.

node2 - the String of the second node.

Returns:

the Object representing the edge relationship.

getEdge

public Edge getEdge(Node source,
                    Node destination)

Locates an Edge object in the edgeList and returns it. Note that it will also return an edge with the provided source and destination parameters swapped IF AN ONLY IF said edge is undirected.

Parameters:

source - the source Node of the edge.

destination - the destination Node of the edge.

Returns:

the Edge object or null if not found.

getEdgeList

public java.util.List<Edge> getEdgeList()

Returns the list of edges in the graph.

Returns:

the List<Edge> containing the list of edges in the graph.

addPartialGraph

public boolean addPartialGraph(java.util.List<Node> nodes,
                               java.util.List<Edge> edges)

Adds a partial graph to this graph. Specifically adds a set of nodes and a set of edges to the graph. It should be noted that nodes or edges in the graph already that attempt to be added again may cause exceptions to occur. Additionally, Nodes are added before Edges so any Edges that depend on Nodes in the add list may be safely added simultaneously. This method is the backbone structure for adding any component to the graph as all other addition methods filter through here.

Parameters:

nodes - the List<Node> containing the nodes to add.

edges - the List<Edge> containing the edges to add.

Returns:

true, always. Allows overriding in subclasses which wish to change base implementation.

getSubGraph

public Graph getSubGraph(int startNode,
                         int stopNode,
                         java.lang.String nameQualifier)

Deprecated. Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)

Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.

Parameters:

startNode - the integer pointing to the start node.

stopNode - the integer pointing to the stop node.

nameQualifier - the String representing an additional qualifier to prepend the name of the new Graph object with.

Returns:

the Graph object representing a subgraph of the original.

getSubGraph

public Graph getSubGraph(java.util.ArrayList<java.lang.String> subStringSet,
                         java.lang.String nameQualifier)

Deprecated. Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)

Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.

Parameters:

subStringSet - an ArrayList containing the String names of the desired nodes.

nameQualifier - the String representing an additional qualifier to prepend the name of the new Graph object with.

Returns:

the Graph object representing a subgraph of the original.

getSubGraph

public Graph getSubGraph(java.util.List<Node> nodes,
                         java.lang.String nameQualifier)

Returns a subGraph of this graph. Isolates and extracts a subgraph based on a user supplied node list. The new Graph is a quasi-separate Graph. Each node utilized is directly related between the two graphs and, as such, changes to the properties of one node in the subgraph will be reflected in the super graph. To obtain an independent graph

Parameters:

nodes - the List<Node> containing the Node references.

nameQualifier - the String to differentiate the Graph names.

Returns:

the Graph representing the subgraph.

transpose

public void transpose(int node1Index,
                      int node2Index)

Transposes the specified nodes. Swaps the location of the nodes in memory. Specifically swaps the nodes in the nodeList as the Edge data has been uncoupled from the Node data. Newer implementation is dependent upon the int based method for performance.

Parameters:

node1Index - the integer index of the first node.

node2Index - the integer index of the second node.

transpose

public void transpose(java.lang.String node1,
                      java.lang.String node2)

Deprecated. Outdated since v3. Replaced by {}

Transposes the specified nodes. Swaps the location of the nodes in memory. This is a convenience method for transposing the nodes based on the Sting representation of the nodes.

Parameters:

node1 - the String name of the first node.

node2 - the String name of the second node.

transpose

public void transpose(Node node1,
                      Node node2)

Transposes the specified nodes. Relies on the integer based method for carrying out the operation.

Parameters:

node1 - the Node object in the first position.

node2 - the Node object in the second position.

getAdjacencyList

public java.util.List<Node> getAdjacencyList(Node node)

Obtains an adjacency list for the supplied node based on the Graph.

Parameters:

node - the Node to obtain the adjacency list for.

Returns:

the List<Node> containing the adjacent Nodes.

checkNode

private void checkNode(Node node)

Verifies that the node is NOT in the graph. Checks to see if the provided node name is in the headerList and, hence, the dataMatrix. This is an internal method used to ensure that the algorithm is operating correctly.

Parameters:

node - the Node to check for.

checkNodeIndex

private void checkNodeIndex(int nodeIndex)

Deprecated. No replacement. Further operations shall utilize {)}

Verifies that the nodeIndex is valid. Ensures that the node does not fall out of bounds. This is an internal method used to ensure that the algorithm is operating correctly.

Parameters:

nodeIndex - the integer of the node to check for.

copy

public Graph copy()

Copies this Graph object using the getSubGraph() method.

Returns:

a Graph object identical to the original.

uniqueCopy

public Graph uniqueCopy()

Copies this Graph producing a unique copy in which there is no entanglement between the two Graph objects. I.e. there are no shared nodes or edges between the two graphs. Mathematically speaking: x.getNodeList().get(0) != y.getNodeList().get(0) under any circumstances. The Nodes and Edges may remain equivalent via the equals() implementation. Further, Edge data shall remain entangled due to implementation details.

Returns:

a unique copy of the graph object.